CS 5010: Problem Set 3

Out: Monday, September 29, 2014

Due: Monday, October 6, 2014 at 600pm local time

The goal of this problem set is to help you design functions that deal with lists.

Remember that you must follow the design recipe. Your deliverables include the data analysis (including template), contract and purpose header, examples, design strategy, code, and tests. You must also include your laboratory notebook.

As you did before, download a copy of extras.rkt and put it in the folder with your solutions. Download any other files that are needed for each problem. Put necessary provide and require directives at the top of your file, as you did before.

Required Exercises

1. Design a program called inventory.rkt, containing a set of functions for manipulating the inventory of a bookstore, represented as a list of books. For each book, we must maintain the following information:
   • isbn, an integer (the "international standard book number"). This serves as a unique identifier for this book. There is an official data definition for ISBN's, but we will simply model them as integers.
   • title, a string
   • author, a string
   • publisher, a string
   • unit price: a non-negative integer, the price at which we will sell the book (in USD*100, ie $14.99 is represented as 1499).
   • unit cost: a number, the cost of the book to the bookstore in USD*100, also a non-negative integer
   • number of copies on hand
   • re-order status. Our bookstore periodically reorders books from the publisher. For each book, there is at most one outstanding reorder. If there is no reorder, the reorder status must represent this information. If there is a reorder, the re-order status contains the number of days until the the next shipment of this book is expected to arrive, and the number of copies expected to arrive at that time. Both of these are positive integers.
   • cuft: the volume taken up by one unit of this item, in cubic feet.

   The inventory satisfies the invariant that there are no duplicates: any isbn appears at most once in the inventory. In this problem set, we don't provide any way to add or remove books (ISBNs) from the inventory, although we do model changing the number of copies of an ISBN that are currently in stock.

   You also need to deal with orders. An order is a list of line items. A line item consists of an ISBN and the quantity ordered. The quantity ordered is always a positive integer. Here is an example of an order; each line of the table is a line item. Here is an example of how an order might be displayed as a table.

   ISBN	Quantity
   45861387	3
   19968208	15
   30581274	10

   Like the inventory, an order will contain no duplicate line items: any isbn will occur at most once in an order.

   Also, for this problem, we introduce the Data Definition MaybeInteger

   ;; A MaybeInteger is one of:
   ;; -- Integer
   ;; -- false
   

   Design the following functions.

   All functions that return an inventory should return an inventory with the books in the same order they were in the argument.

   Your solution should provide the following functions:

   inventory-potential-profit : Inventory ->  Integer
   GIVEN: an inventory
   RETURNS: the total profit, in USD*100, for all the items in stock (i.e., how much
   the bookstore would profit if it sold every book in the inventory).
   
   inventory-total-volume : Inventory -> Real
   GIVEN: an inventory
   RETURNS: the total volume needed to store all the books in the inventory
   
   price-for-line-item : Inventory LineItem -> MaybeInteger
   GIVEN: an inventory and a line item
   RETURNS: the price for that line item (the quantity times the unit
   price for that item).  Returns false if that isbn does not exist in
   the inventory. 
   
   fillable-now? : Order Inventory -> Boolean.
   GIVEN: an order and an inventory
   RETURNS: true iff there are enough copies of each book on hand to fill
   the order.  If the order contains a book that is not in the inventory,
   then the order is not fillable.
   
   days-til-fillable : Order Inventory -> MaybeInteger
   GIVEN: an order and an inventory
   RETURNS: the number of days until the order is fillable, assuming all
   the shipments come in on time.  Returns false if there won't be enough
   copies of some book, even after the next shipment of that book comes
   in.
   EXAMPLES: if the order contains one book that is out of stock, with a
   reorder status showing 2 days until delivery, then the order is
   fillable in 2 days.  If the order is for 10 copies of the book, and
   the next order consists of only 5 books, then the function should return false.
   
   price-for-order : Inventory Order -> NonNegInteger
   RETURNS: the total price for the given order, in USD*100.  The price does not
   depend on whether any particular line item is in stock.  Line items
   for an ISBN that is not in the inventory count as 0.
   
   inventory-after-order : Inventory Order -> Inventory.
   GIVEN: an inventory and an order
   WHERE: the order is fillable now
   RETURNS: the inventory after the order has been filled.
   
   increase-prices : Inventory String Real -> Inventory
   GIVEN: an inventory, a publisher, and a percentage,
   RETURNS: an inventory like the original, except that all items by that
   publisher have their unit prices increased by the specified
   percentage. If the increased price is a non-integer, it may be either
   raised to the next integer price, or truncated to the next lowest
   integer price in USD*100.
   EXAMPLE: (increase-prices inventory1 "MIT Press" 10)
   returns an inventory like the original, except that all MIT Press
   books in the inventory have had their prices increased by 10%.
   
   Also provide the functions:
   
   make-book  (9 arguments)
   make-line-item (2 arguments)
   The arguments to these functions should appear in the same order as
   they do in the problem statement.
   
   reorder-present? : ReorderStatus -> Boolean
   RETURNS: true iff the given ReorderStatus shows a pending re-order.
   
   make-empty-reorder : Any -> ReorderStatus
   Ignores its argument
   RETURNS: a ReorderStatus showing no pending re-order. 
   
   make-reorder : PosInt PosInt -> ReorderStatus
   GIVEN: a number of days and a number of copies
   RETURNS: a ReorderStatus with the given data.
   

   Before you turn in your solution, make sure it passes the tests in ps03-inventory-qualification.rkt. As before, download this file, save it in your set03 directory, and run it to qualify your program for grading. Be sure to commit this file to your repository so we know that you've done this correctly.

   For what it's worth, students in previous semesters have solved variations of this problem in a median time of 12-15 hours.

2. (Balls in a Box). Write a program called balls-in-box.rkt that meets the following requirements:
   • Your program should display some balls that you can drag on a canvas.
   • The program starts with a canvas 400 pixels wide and 300 pixels high, with no balls.
   • Hitting the "n" key should create a new ball in the center of the canvas.
   • You can select a ball by doing a button-down inside the ball. When a ball is selected, you can drag it with the mouse. It becomes unselected when you do a mouse-up. The ball should be smoothly draggable, like the rectangle in problem set 2.
   • The balls should be displayed as a circle with radius 20. An unselected ball should be displayed as an outline; a selected ball should be displayed solid. Unlike the draggable rectangle from last week, you should NOT display the position of the mouse within the ball.
   • In addition to the balls, you should display the number of balls currently on the canvas.
   • As before, you may assume the mouse is never dragged outside of the canvas.

   Your program should provide the following functions:

   run : Any -> World
   GIVEN: An argument, which is ignored.
   EFFECT: runs the world at tick rate of 0.25 secs/tick.
   RETURNS: the final state of the world.
   Note that the world does not respond to time passing, so the tick rate
   doesn't make a difference.
   
   initial-world : Any  -> World
   GIVEN: An argument, which is ignored.
   RETURNS: a world with no balls.
   
   world-after-key-event : World KeyEvent -> World
   RETURNS: the world that should follow the given world after the given
   key event.
   
   world-after-mouse-event : World Integer Integer MouseEvent -> World
   GIVEN: A world, the location of a mouse event, and the mouse event itself
   RETURNS: the world that should follow the given world after the given
   mouse event at the given location.
   
   world-balls : World -> ListOfBalls
   GIVEN: a world,
   RETURNS: the list of balls that are in the box.
   
   ball-x-pos : Ball -> Integer
   ball-y-pos : Ball -> Integer
   GIVEN: a ball
   RETURNS: the x or y position of its center, respectively.
   
   ball-selected? : Ball -> Boolean
   GIVEN: a ball
   RETURNS: true if and only if it is currently selected
   

   Note: if any of these functions are implemented as selectors on structs, then you don't need to provide the design recipe deliverables for them.

   If any function is just a renaming of an extractor, for example

   (define-struct ball (x y ...))
   ...
   (define (ball-x-pos b)
     (ball-x b))
   

   then you need to deliver a contract and purpose statement, but you don't need examples, strategy, or tests.

   Before you turn in your solution, make sure it passes the tests in ps03-balls-in-box-qualification.rkt. As before, download this file, save it in your set03 directory, and run it to qualify your program for grading. Be sure to commit this file to your repository so we know that you've done this correctly.

   For what it's worth, my solution to this problem was 263 lines, exclusive of tests. In Fall 2013, students solved a closely related problem of comparable difficulty in a median time of 12.8 hours.